﻿// 0825train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using namespace std;

/*
 某个时间段内的接口失败率使用一个数组表示，
 数组中每个元素都是单位时间内失败率数值，数组中的数值为 0~100 的整数，
 给定一个数值(minAverageLost)表示某个时间段内平均失败率容忍值，
 即平均失败率小于等于 minAverageLost，找出数组中最长时间段，如果未找到则直接返回 NULL

输入描述
输入有两行内容，第一行为minAverageLost，第二行为数组，数组元素通过空格" "分隔，
minAverageLost 及数组中元素取值范围为 0~100 的整数，数组元素的个数不会超过 100 个

输出描述
找出平均值小于等于 minAverageLost 的最长时间段，输出数组下标对，
格式{beginIndex}-{endIndx}(下标从 0 开始)，
如果同时存在多个最长时间段，则输出多个下标对且下标对之间使用空格" "拼接，多个下标对按下标从小到大排序

示例1
1
0 1 2 3 4
输出
0-2

说明
A、输入解释：minAverageLost=1，数组[0, 1, 2, 3, 4]
B、前 3 个元素的平均值为 1，因此数组第一个至第三个数组下标，即 0-2
 */

class Solution01
{
public:
    vector<int>prev_sum;
    vector<pair<int,int>>result;
    Solution01(vector<int>&nums_vec, int aver_limit)
    {
        aver_limit_ = aver_limit;
        nums_size_ = nums_vec.size();
        prev_sum.resize(nums_size_ + 1);
        for (int i=0; i<prev_sum.size()-1; i++)
        {
            prev_sum[i + 1] = prev_sum[i] + nums_vec[i];
        }
    }

    int getSumRange(int left, int right)
    {
        return prev_sum[right] - prev_sum[left];
    }

    void solve01()
    {
        //0-2 (prev_sum[right+1]-prev_sum[left])/(right-left+1)
		for (int length=prev_sum.size()-1; length>=0; length--)
		{
            for (int i=0; i<prev_sum.size(); i++)
            {
                if (i+length>=prev_sum.size())
                {
                    break;
                }

                int upper_limit = aver_limit_ * length;
                if (getSumRange(i,i+length)<=upper_limit)
                {
                    if (length>curr_max_)
                    {
                        result.clear();
                        result.push_back(make_pair(i, i + length - 1));
                        curr_max_ = length;
                    }
                    else if (length==curr_max_)
                    {
                        result.push_back(make_pair(i, i + length - 1));
                    }

                }

            }
			
		}

        if (result.empty())
        {
            cout << "NULL";
        }
        else if (result.size()==1)
        {
            cout << result[0].first << '-' << result[0].second;
        }
        else
        {
            for (int i=0; i<result.size();i++)
            {
                cout << result[i].first << '-' << result[i].second;
                if (i!=result.size()-1)
                {
                    cout << ' ';
                }
            }

        }
        

    }
private:
    int curr_max_ = 0;
    int aver_limit_ = 0;
    int nums_size_ = 0;
};


/*
每个积木块上都有一个数字，积木块上的数字可能相同
小华随机拿一些积木挨着排成一排，
找到这排积木中数字相同且所处位置最远的 2 块积木块，计算他们的距离

输入
第一行输入为 N ，表示小华排成一排的积木总数
接下来 N 行每行一个数字，表示小花排成一排的积木上数字
输出
相同数字的积木的位置最远距离；如果所有积木数字都不相同，请返回 -1

输入
5
1
2
3
1
4
输出
3
 */
class Solution02
{
public:
    int max_length = 0;
    Solution02(vector<int>&nums_vec)
    {
        for (int length=nums_vec.size()-1; length>=0; length--)
        {
            for (int start = 0; start < nums_vec.size(); start++)
            {
                if (start+length>=nums_vec.size())
                {
                    break;
                }

                if (nums_vec[start] == nums_vec[start + length])
                {
                    max_length = max(max_length, length);

                }

            }

        }
        if (max_length==0)
        {
            cout << -1;
            return;
        }

        cout << max_length;
        //Solution02
    }
};


/*
 alolobo
 */
class Solution03
{
public:
    vector<int>pre_sum;
    int max_length = 0;
    Solution03(string&origin_str)
    {
        str_size_ = origin_str.size();
        pre_sum.resize(str_size_ + 1);

        //l 4 o 2 x 1
        unordered_map<char, int>char_map = { {'l',4},{'o',2},{'x',1} };
        for (int i=0; i< str_size_; i++)
        {
            char curr_char = origin_str[i];
			if (char_map.count(curr_char)>0)
			{
                pre_sum[i + 1] = pre_sum[i] ^ char_map[curr_char];
			}
        }

    }
    void solve03()
    {
        for (int length = pre_sum.size()-1; length>=0; length--)
        {
	        for (int i=0; i<pre_sum.size();i++)
	        {
                if (i + length >= pre_sum.size()) break;

                if (pre_sum[i]==pre_sum[i+length])
                {
                    curr_max_ = max(curr_max_, length);
                }

	        }
        }
        cout << curr_max_;
    }
private:
    int str_size_ = 0;
    int curr_max_ = 0;
};


class Solution13
{
public:
    vector<int>pre_sum;
    int max_length = 0;
    Solution13(string& origin_str)
    {
        origin_str_ = origin_str;
        string ring_str = origin_str+ origin_str;
        str_size_ = ring_str.size();
        pre_sum.resize(str_size_ + 1);

        //l 4 o 2 x 1
        unordered_map<char, int>char_map = { {'l',4},{'o',2},{'x',1} };
        for (int i = 0; i < str_size_; i++)
        {
            char curr_char = ring_str[i];
            if (char_map.count(curr_char) > 0)
            {
                pre_sum[i + 1] = pre_sum[i] ^ char_map[curr_char];
            }
            else
            {
                pre_sum[i + 1] = pre_sum[i];
            }
        }

    }
    void solve03()
    {
        int size_limit = origin_str_.size();
        unordered_map<int, deque<int>>prev_map; //存储相同元素的坐标

        for (int i=0; i<pre_sum.size(); i++)
        {
            int curr_num = pre_sum[i];
            prev_map[curr_num].push_back(i);

            while ((!prev_map[curr_num].empty()) && (i - prev_map[curr_num].front()) > size_limit)
            {
                prev_map[curr_num].pop_front();
            }

            curr_max_ = max(curr_max_, i - prev_map[curr_num].front());
        }

        cout << curr_max_;
    }
private:
    string origin_str_;
    int str_size_ = 0;
    int curr_max_ = 0;
};


int main()
{
	{
        //alolobo
        //string str = "alolobo";
        string str;
        getline(cin, str);
        Solution13 solu(str);
        solu.solve03();

        return 0;
	}
/*
5
1
2
3
1
4
*/
	{
        int vec_size;
        cin >> vec_size;
        vector<int>nums_vec(vec_size);

        for (int i=0; i<vec_size; i++)
        {
            cin >> nums_vec[i];
        }

        //vector<int>nums_vec = { 1,2,3,5,4 };
        Solution02 solu(nums_vec);

        return 0;
	}
/*
示例1
1
0 1 2 3 4
输出
0-2

示例2
2
0 0 100 2 2 99 0 2
输出
0-1 3-4 6-7

35
54 62 78 45 59 92 93 8 12 58 84 19 46 79 96 82 42 41 5 2 31 12 46 54
 */
    int aver_limit;
    cin >> aver_limit;
    cin.ignore();
    vector<int>nums;
    string input;
    getline(cin, input);
    //string input = "54 62 78 45 59 92 93 8 12 58 84 19 46 79 96 82 42 41 5 2 31 12 46 54";
    string token;
    stringstream oh_sstream(input);
    while (oh_sstream>>token)
    {
        nums.push_back(stoi(token));
    }

    //int aver_limit = 35;
    //vector<int>nums = { 0,1,2,3,4 };
    Solution01 solu(nums, aver_limit);
    solu.solve01();

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
